class Solution 
{
public:
    vector<vector<int>> threeSum(vector<int>& nums) 
    {
        // 1、初始化
        int n = nums.size();
        vector<vector<int>> ret;
        // 2、排序
        sort(nums.begin(), nums.end());
        // 3、依次固定一个数
        for(int i = 0; i < n - 2;)
        {
            // 4、双指针算法找到两数之和等于 aim 的元素
            int left = i + 1, right = n - 1, aim = -nums[i];
            while(left < right)
            {
                int sum = nums[left] + nums[right];
                if(sum < aim) ++left;
                else if(sum > aim) --right;
                else 
                {
                    ret.push_back( {nums[i], nums[left], nums[right]} );
                    ++left, --right; // 保证 left、right 选择的元素不漏
                    // 对 left、right 已经选择过的元素去重
                    while(left < right && nums[left] == nums[left - 1]) ++left;
                    while(left < right && nums[right] == nums[right + 1]) --right;
                }
            }
            // 保证 i 选择的元素不漏
            ++i; 
            // 对 i 已经选择过的元素去重
            while(i < n - 2 && nums[i] == nums[i - 1]) ++i;
        }
        // 5、返回最终结果
        return ret;
    }
};
/*
- 时间复杂度：O(n^2)
- 空间复杂度：O(1)
*/
